努力踏出程式舒適圈的我
之前在coding的時候一直沒有遇到需要使用dp的場合
真是應該反思，到底是我菜到別人不敢要我寫需要dp的東西，還真的是用不到呢？

55. Jump Game (medium)

https://leetcode.com/problems/jump-game/
Submission：https://leetcode.com/problems/jump-game/submissions/857775682/
You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.
nums裡的值代表可以從目前位置 i 到 i + nums[i]的點位，要檢查是否可以抵達最後的點位

class Solution:
    #nums裡的值代表可以從目前位置 i 到 i + nums[i]的點位
    #檢查最後是否可以到最後的點位

    #感覺是抓每一格最大可以走到多遠
    #自己寫的，但感覺怪怪的，比起dp這更像貪婪
    def canJump(self, nums: List[int]) -> bool:
        dp = [-1]*len(nums)
        newNums = [i+nums[i] for i in range(len(nums))]
        i = 0
        while 1:
            temp = newNums[i]
            if temp >= len(nums)-1:
                return 1
            tempList = newNums[i:temp+1]
            maxNum = max(tempList)
            if maxNum <= newNums[i]:
                return 0
            i += tempList.index(maxNum)

class Solution:
    #幹，想到這寫法的人好聰明喔
    #我有想到擦邊，但沒想到可以這樣寫
    def canJump(self, nums: List[int]) -> bool:
        last_position = len(nums)-1 #最後一個位置
        for i in range(len(nums)-2,-1,-1): #從倒數第二開始往前跑
            if (i + nums[i]) >= last_position: #往前跑時，如果那個位置可以到達終點，就把他當成最後一個位置
                last_position = i
        return last_position == 0	

45. Jump Game II (medium)

https://leetcode.com/problems/jump-game-ii/
Submission：https://leetcode.com/problems/jump-game-ii/submissions/857794341/
You are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0].

Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at nums[i], you can jump to any nums[i + j] where:

0 <= j <= nums[i] and
i + j < n
Return the minimum number of jumps to reach nums[n - 1]. The test cases are generated such that you can reach nums[n - 1].
必定可以跳到終點，要檢查最小的跳躍數是多少，比起jump game麻煩的地方在於要統計次數

class Solution:
    # 必定可以跳到終點
    # 要檢查最小的跳躍數是多少

    # 直接從第0個開始加
    # 一開始寫的，有機會TLE
    def jump(self, nums: List[int]) -> int:
        ans = 0
        nL = len(nums)
        dp = [0]+[float("inf") for i in range(nL-1)]
        for i in range(nL):
            for j in range(i+1,i+nums[i]+1):
                if j < nL:
                    dp[j] = min(dp[j],dp[i]+1)
        print(dp)
        return dp[-1]

class Solution:
    def jump(self, nums):
        if len(nums) <= 1: return 0
        l, r = 0, nums[0]#起始點跟終點
        times = 1 #一開始一定跑一次
        while r < len(nums) - 1:
            times += 1
            nxt = max(i + nums[i] for i in range(l, r + 1))
            #直接抓可以跑最遠的點
            #後來思考一下，因為跑最遠的點一定離終點最近，反之所需步數必為最少
            l, r = r, nxt
        return times

1708. Largest Subarray Length K (easy)

https://leetcode.com/problems/largest-subarray-length-k/
Submission：https://leetcode.com/problems/largest-subarray-length-k/submissions/857795997/

An array A is larger than some array B if for the first index i where A[i] != B[i], A[i] > B[i].

For example, consider 0-indexing:

[1,3,2,4] > [1,2,2,4], since at index 1, 3 > 2.
[1,4,4,4] < [2,1,1,1], since at index 0, 1 < 2.
A subarray is a contiguous subsequence of the array.

Given an integer array nums of distinct integers, return the largest subarray of nums of length k.
找最大的subarray(以subarray[0]進行比較)k為subarray的長度

class Solution:
    #找最大的subarray(以subarray[0]進行比較)
    #k為subarray的長度
    def largestSubarray(self, nums: List[int], k: int) -> List[int]:
        index,maxNum =0,0
        for i in range(len(nums)-k+1):
            if nums[i] > maxNum:
                maxNum = nums[i]
                index = i
        return nums[index:index+k]

1826. Faulty Sensor

https://leetcode.com/problems/faulty-sensor/
Submission：https://leetcode.com/problems/faulty-sensor/submissions/857800249/
An experiment is being conducted in a lab. To ensure accuracy, there are two sensors collecting data simultaneously. You are given two arrays sensor1 and sensor2, where sensor1[i] and sensor2[i] are the ith data points collected by the two sensors.

However, this type of sensor has a chance of being defective, which causes exactly one data point to be dropped. After the data is dropped, all the data points to the right of the dropped data are shifted one place to the left, and the last data point is replaced with some random value. It is guaranteed that this random value will not be equal to the dropped value.

For example, if the correct data is [1,2,3,4,5] and 3 is dropped, the sensor could return [1,2,4,5,7] (the last position can be any value, not just 7).
We know that there is a defect in at most one of the sensors. Return the sensor number (1 or 2) with the defect. If there is no defect in either sensor or if it is impossible to determine the defective sensor, return -1.

兩個傳感器，其中一個傳感器的數據有缺失，找出缺失的傳感器

class Solution:
    #兩個傳感器
    #其中一個傳感器的數據有缺失
    #找出缺失的傳感器

    #有可能有種特別的狀況，無論是sensor1或sensor2後面長個都相同
    def badSensor(self, sensor1: List[int], sensor2: List[int]) -> int:
        sL = len(sensor1)
        for i in range(sL):
            if sensor1[i] != sensor2[i] and i != sL-1:
                tempS1F,tempS1S = sensor1[i:-1],sensor1[i+1:]
                tempS2F,tempS2S = sensor2[i:-1],sensor2[i+1:]
                if tempS1F == tempS2S and tempS1S == tempS2F:
                    return -1
                elif tempS1F == tempS2S:
                    return 1
                elif tempS2F == tempS1S:
                    return 2
        return -1